Representing Connections in a Graph

Graphs are abstract structures of nodes and edges. To use them in a program, we need concrete data structures. The two most common are Adjacency Lists and Adjacency Matrices, each with distinct trade-offs.

Adjacency List: An array where each index corresponds to a vertex. The element at that index is a list of all vertices it connects to.
- Pros: Space-efficient for sparse graphs (few edges), with space complexity of $O(V+E)$ . Iterating over a vertex's neighbors is fast.
- Cons: Checking for a specific edge $(u, v)$ can be slow, taking up to $O(\text{degree}(u))$ time.
Adjacency Matrix: A $V \times V$ matrix where cell $(i, j)$ is 1 if an edge exists from vertex $i$ to $j$ , and 0 otherwise.
- Pros: Extremely fast edge lookup, taking $O(1)$ time. Well-suited for dense graphs (many edges).
- Cons: Requires $O(V^2)$ space regardless of the number of edges, which is very inefficient for sparse graphs.

📝 Interactive Quiz

1. What is the time complexity to check if an edge exists between two vertices in an Adjacency Matrix?

A) $O(1)$
B) $O(V)$
C) $O(E)$
D) $O(V+E)$

2. What is the space complexity of an Adjacency List for a graph with $V$ vertices and $E$ edges?

A) $O(V^2)$
B) $O(E^2)$
C) $O(V+E)$
D) $O(V \times E)$

3. For which type of graph is an Adjacency Matrix generally more space-efficient?

A) Sparse graphs (few edges)
B) Dense graphs (many edges)
C) Directed Acyclic Graphs
D) Bipartite graphs

4. You are modeling a social network with millions of users but relatively few connections per user. Which representation is better?

A) Adjacency Matrix
B) Adjacency List

KEY TIPS

💡 Quick Tips

Directed vs. Undirected

Matrix: An undirected graph has a symmetric matrix ( $A[i][j] = A[j][i]$ ).
List: For an undirected edge $(u, v)$ , $v$ is in $u$ 's list and $u$ is in $v$ 's list.

Weighted Edges

To store weights:

Matrix: Store the weight $W_{i, j}$ instead of 1. Use $\infty$ for non-edges.
List: Store pairs of $(\text{neighbor}, \text{weight})$ in the lists.

The Sparse vs. Dense Rule

A simple rule of thumb: if the number of edges

E

is close to

V^2

, the graph is dense (use a matrix). If

E

is much closer to

V

, it's sparse (use a list).